// Copyright 2013 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef NET_SPDY_WRITE_BLOCKED_LIST_H_
#define NET_SPDY_WRITE_BLOCKED_LIST_H_

#include <stddef.h>

#include <algorithm>
#include <deque>
#include <unordered_map>

#include "base/logging.h"
#include "net/spdy/spdy_bug_tracker.h"
#include "net/spdy/spdy_protocol.h"

namespace net {

namespace test {
    class WriteBlockedListPeer;
} // namespace test

template <typename IdType>
class WriteBlockedList {
public:
    // 0(1) size lookup.  0(1) insert at front or back.
    typedef std::deque<IdType> BlockedList;
    typedef typename BlockedList::iterator iterator;

    WriteBlockedList() { }

    static SpdyPriority ClampPriority(SpdyPriority priority)
    {
        if (priority < kV3HighestPriority) {
            SPDY_BUG << "Invalid priority: " << static_cast<int>(priority);
            return kV3HighestPriority;
        }
        if (priority > kV3LowestPriority) {
            SPDY_BUG << "Invalid priority: " << static_cast<int>(priority);
            return kV3LowestPriority;
        }
        return priority;
    }

    // Returns the priority of the highest priority list with sessions on it.
    SpdyPriority GetHighestPriorityWriteBlockedList() const
    {
        for (SpdyPriority i = 0; i <= kV3LowestPriority; ++i) {
            if (write_blocked_lists_[i].size() > 0) {
                return i;
            }
        }
        SPDY_BUG << "No blocked streams";
        return kV3HighestPriority;
    }

    IdType PopFront(SpdyPriority priority)
    {
        priority = ClampPriority(priority);
        DCHECK(!write_blocked_lists_[priority].empty());
        IdType stream_id = write_blocked_lists_[priority].front();
        write_blocked_lists_[priority].pop_front();
        stream_to_priority_.erase(stream_id);
        return stream_id;
    }

    bool HasWriteBlockedStreamsGreaterThanPriority(SpdyPriority priority) const
    {
        priority = ClampPriority(priority);
        for (SpdyPriority i = kV3HighestPriority; i < priority; ++i) {
            if (!write_blocked_lists_[i].empty()) {
                return true;
            }
        }
        return false;
    }

    bool HasWriteBlockedStreams() const
    {
        for (SpdyPriority i = kV3HighestPriority; i <= kV3LowestPriority; ++i) {
            if (!write_blocked_lists_[i].empty()) {
                return true;
            }
        }
        return false;
    }

    // Add this stream to the back of the write blocked list for this priority
    // level.  If the stream is already on that write blocked list this is a
    // no-op.  If the stream is on a write blocked list for a different priority
    // it will be removed from that list.
    void PushBack(IdType stream_id, SpdyPriority priority)
    {
        AddStream(stream_id, priority, true);
    }

    // Add this stream to the front of the write blocked list for this priority
    // level.  If the stream is already on that write blocked list this is a
    // no-op.  If the stream is on a write blocked list for a different priority
    // it will be removed from that list.
    void PushFront(IdType stream_id, SpdyPriority priority)
    {
        AddStream(stream_id, priority, false);
    }

    bool RemoveStreamFromWriteBlockedList(IdType stream_id,
        SpdyPriority priority)
    {
        typename StreamToPriorityMap::iterator iter = stream_to_priority_.find(stream_id);
        if (iter == stream_to_priority_.end()) {
            // The stream is not present in the write blocked list.
            return false;
        } else if (iter->second == priority) {
            stream_to_priority_.erase(iter);
        } else {
            // The stream is not present at the specified priority level.
            return false;
        }
        // We shouldn't really add a stream_id to a list multiple times,
        // but under some conditions it does happen. Doing a check in PushBack
        // would be too costly, so instead we check here to eliminate duplicates.
        bool found = false;
        iterator it = std::find(write_blocked_lists_[priority].begin(),
            write_blocked_lists_[priority].end(), stream_id);
        while (it != write_blocked_lists_[priority].end()) {
            found = true;
            iterator next_it = write_blocked_lists_[priority].erase(it);
            it = std::find(next_it, write_blocked_lists_[priority].end(), stream_id);
        }
        return found;
    }

    void UpdateStreamPriorityInWriteBlockedList(IdType stream_id,
        SpdyPriority old_priority,
        SpdyPriority new_priority)
    {
        if (old_priority == new_priority) {
            return;
        }
        bool found = RemoveStreamFromWriteBlockedList(stream_id, old_priority);
        if (found) {
            PushBack(stream_id, new_priority);
        }
    }

    size_t NumBlockedStreams() const
    {
        size_t num_blocked_streams = 0;
        for (SpdyPriority i = kV3HighestPriority; i <= kV3LowestPriority; ++i) {
            num_blocked_streams += write_blocked_lists_[i].size();
        }
        return num_blocked_streams;
    }

    size_t NumBlockedStreams(SpdyPriority priority) const
    {
        priority = ClampPriority(priority);
        return write_blocked_lists_[priority].size();
    }

private:
    friend class net::test::WriteBlockedListPeer;

    using StreamToPriorityMap = std::unordered_map<IdType, SpdyPriority>;

    void AddStream(IdType stream_id, SpdyPriority priority, bool push_back)
    {
        priority = ClampPriority(priority);
        DVLOG(2) << "Adding stream " << stream_id << " at priority "
                 << static_cast<int>(priority);
        bool should_insert_stream = true;
        typename StreamToPriorityMap::iterator iter = stream_to_priority_.find(stream_id);
        // Ensure the stream is not in the write blocked list multiple times.
        if (iter != stream_to_priority_.end()) {
            DVLOG(1) << "Stream " << stream_id << " already in write blocked list.";
            if (iter->second == priority) {
                // The stream is already in the write blocked list for the priority.
                // It will not be inserted again but will retain its place in the list.
                should_insert_stream = false;
            } else {
                // The stream is in a write blocked list for a different priority.
                // Remove it from that list and allow it to be added to the list for
                // this priority.
                bool removed = RemoveStreamFromWriteBlockedList(stream_id, iter->second);
                DCHECK(removed);
            }
        }
        if (should_insert_stream) {
            stream_to_priority_[stream_id] = priority;
            if (push_back) {
                write_blocked_lists_[priority].push_back(stream_id);
            } else {
                write_blocked_lists_[priority].push_front(stream_id);
            }
        }
    }
    BlockedList write_blocked_lists_[kV3LowestPriority + 1];
    StreamToPriorityMap stream_to_priority_;
};

} // namespace net

#endif // NET_SPDY_WRITE_BLOCKED_LIST_H_
